/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 插入.链表;

/**
 * @Description 插入排序
 * 是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
 * 链表实现
 * <p>
 * 链表的添加就是插入排序的第二个过程
 * @Author 俊昭
 * @Date 2022/4/30
 */
public class Insertion {

    private static final Node head = new Node(- 10086);

    /**
     * @param arr 接收的数组
     * @description 接受一个数组将其转为链表储存
     * @author 俊昭
     * @date 2022/4/30
     */
    public static void sort(int[] arr) {
        for (int j : arr) {
            add(new Node(j));
        }
//        show();
    }

    /**
     * @description 遍历输出链表
     * @author 俊昭
     * @date 2022/4/30
     */
    private static void show() {
        Node temp = head.next;
        while (temp != null) {
            System.out.print(temp + " ");
            temp = temp.next;
        }
    }

    /**
     * @param newNode 一个新的Node对象
     * @description 将新对象加入链表的逻辑
     * @author 俊昭
     * @date 2022/4/30
     */
    private static void add(Node newNode) {
        Node temp = head;
        int no = newNode.num;
        while (true) {
            if (no == temp.num) {
                newNode.next = temp.next;
                temp.next = newNode;
                break;
            } else if (temp.next == null) {
                temp.next = newNode;
                break;
            } else if (no > temp.num && no < temp.next.num) {
                newNode.next = temp.next;
                temp.next = newNode;
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * @author 俊昭
     * @description 链表的单位节点
     * @date 2022/4/30
     */
    private static class Node {
        int num;
        Node next;

        public Node(int num) {
            this.num = num;
        }

        @Override
        public String toString() {
            return num + "";
        }
    }
}
